package simple;

import java.util.Objects;
import java.util.Stack;

/**
 * 155. 最小栈
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。<br />
 * <p>
 * 如何在常数时间内获取栈内最小的元素<br />
 * 如果没有时间限制的话，我们可以遍历去查找最小的元素。<br />
 * 但是限制在常数时间的，那我们就需要将最小元素记录下来。<br />
 * 我们不能只靠一个变量去记录最小元素，因为当调用pop把最小元素弹出去以后，这个变量就失效了。<br />
 * 当再一次调用getMin的时候，最小元素就无从得知了。<br />
 * <p>
 * 所以我们需要一个容器去记录最小元素。<br />
 * 当入栈时，我们判断这个元素是否比容器中上一个加入的元素要小。<br />
 * 当这个元素比上一个元素小时，就加入到最小元素容器中。<br />
 * 我们每一次调用getMin函数时，直接将该容器最后一个加入的元素返回即可。<br />
 * <p>
 * 说到这里，这个容器大致是什么数据结构，已经很清楚了。<br />
 * 那就是使用栈！我们使用辅助栈来记录最小元素。<br />
 */
public class MinStack {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public MinStack() {

    }

    public void push(int val) {
        stack1.push(val);
        if (stack2.isEmpty() || val <= stack2.peek()) {
            stack2.push(val);
        }
    }

    public void pop() {
        Integer pop = stack1.pop();
        if (Objects.equals(pop, stack2.peek())) {
            stack2.pop();
        }
    }

    public int top() {
        return stack1.peek();
    }

    public int getMin() {
        return stack2.peek();
    }
}